﻿/*
 *	Filename: wuyaowei_detect_loop.c
 *	 Version: 0.1.0
 *   Description: 链表环检测
 *
 *        Author: wuyaowei
 *          Date: 2020-06-17
 *
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct Node{
  int data;
  struct Node * next;
}Node;

/*
 *  创建节点
 */
Node * createNode(char val) {
  Node *node = (Node *)malloc(sizeof(Node));
  node->data = val;
  node->next = NULL;
  return node;
}

Node *head = NULL;

/*
 * 快慢指针检测环
 */
int detectLoop(Node *head) {
  Node *fast = head;
  Node *slow = head;

  while(NULL != fast && NULL != fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) {
	return 1;
    }
  }

  return 0;
}

void main() {
  int L = 0, N = 0;
  printf("输入链表长度：\n");
  scanf("%d", &L);
  printf("输入环的首节点坐标(0代表没有环)：\n");
  scanf("%d", &N);
  //初始化单链表
  Node *T = NULL, *p = NULL;
  if (N == 0) {
    for (int i = 0; i < L; i++) {
      Node *t1 = createNode(i);
      if (i == 0) {
        head = t1;
        p = t1;
        continue;
      }
      p->next = t1;
      p = t1;
    }
  } else {
    for (int i = 0; i < L; i++) {
      Node *t1 = createNode(i);
      if (i == (N-1)) {
        T = t1;
      }
      if ((i == 0)) {
        head = t1;
        p = t1;
        continue;
      }
      p->next = t1;
      p = t1;
    }
    p->next = T;
  }

  if(detectLoop(head)) {
    printf("链表中存在环\n");
  } else {
    printf("链表中不存在环\n");
  }
}
